package tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树功能实现
 * 
 * @author fix
 *
 */
public class BinaryTree {

	private TreeNode root; // 根节点
	private List<TreeNode> tree = null; // 二叉树节点的链式结构

	// 把一个数组转化为一颗完全二叉树
	public TreeNode buildTree(Object[] array) {
		// 首先将数组以节点的形式存到tree中,使用LinkedList的原因:LinkedList可以用作栈、队列，插入删除比较便利
		tree = new LinkedList<TreeNode>();
		for (int i = 0; i < array.length; i++) {
			tree.add(new TreeNode(array[i]));
		}

		int last = array.length / 2 - 1; // 最后一个父节点
		for (int i = 0; i < last; i++) {
			tree.get(i).setLchild(tree.get(2 * i + 1));
			tree.get(i).setRchild(tree.get(2 * i + 2));
		}
		// 构造最后一个节点
		tree.get(last).setLchild(tree.get(2 * last + 1));
		if (array.length % 2 == 1) { // 有奇数个节点，才会有右儿子
			tree.get(last).setRchild(tree.get(2 * last + 2));
		}
		root = tree.get(0);
		return root;
	}

	// 先序 1 2 4 8 5 3 6 7
	public void preOrder(TreeNode node) {
		if (node != null) {
			System.out.print(node.getData() + " ");
			preOrder(node.getLchild());
			preOrder(node.getRchild());
		}
	}

	// 中序 8 4 2 5 1 6 3 7
	public void inOrder(TreeNode node) {
		if (node != null) {
			inOrder(node.getLchild());
			System.out.print(node.getData() + " ");
			inOrder(node.getRchild());
		}

	}

	// 后序 8 4 5 2 6 7 3 1
	public void postOrder(TreeNode node) {
		if (node != null) {
			postOrder(node.getLchild());
			postOrder(node.getRchild());
			System.out.print(node.getData() + " ");
		}
	}

	public void nonPreOrder(TreeNode node) {
		Stack<TreeNode> nodeStack = new Stack<TreeNode>();
		TreeNode nodeTemp = node; // nodeTemp作为遍历指针
		while (nodeTemp != null || !nodeStack.isEmpty()) { // 当nodeTemp非空或栈非空时循环
			if (nodeTemp != null) { // 根指针非空，遍历左子树
				System.out.print(nodeTemp.getData() + " ");
				nodeStack.push(nodeTemp); // 根指针进栈
				nodeTemp = nodeTemp.getLchild(); // 每遇到非空二叉树先向左走
			} else { // 再向右子树走
				nodeTemp = nodeStack.pop();
				nodeTemp = nodeTemp.getRchild();
			}
		}
	}

	public void nonInOrder(TreeNode node) {
		Stack<TreeNode> nodeStack = new Stack<TreeNode>();
		TreeNode nodeTemp = node; // nodeTemp作为遍历指针
		while (nodeTemp != null || !nodeStack.isEmpty()) {
			if (nodeTemp != null) {
				nodeStack.push(nodeTemp); // 根指针进栈
				nodeTemp = nodeTemp.getLchild();
			} else {
				nodeTemp = nodeStack.pop();
				System.out.print(nodeTemp.getData() + " ");
				nodeTemp = nodeTemp.getRchild();
			}

		}
	}

	// 后序 8 4 5 2 6 7 3 1
	/**
	   先遍历左子树，直到为空时
	   	检查栈头部节点是否有右子树
	   	    
	 */
	public void nonPostOrder(TreeNode node) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode nodeTemp = node;  
		TreeNode last=null ;      //存上一个节点
		while(nodeTemp != null || !stack.isEmpty()) {
			if (nodeTemp!=null) {
				stack.push(nodeTemp);
				nodeTemp=nodeTemp.getLchild();  //先遍历左子树
			}else {
				// 左子树空了
				nodeTemp= stack.peek(); //检查栈头部，但不出栈
				if (nodeTemp.getRchild()!=null && nodeTemp.getRchild()!= last) {
					// 如果节点的右子树不空，且没有访问过
					nodeTemp= nodeTemp.getRchild();
					stack.push(nodeTemp);
					nodeTemp = nodeTemp.getLchild();
				}else {
					nodeTemp = stack.pop();
					last = nodeTemp;
					System.out.print(nodeTemp.getData() + " ");
					nodeTemp = null;
				}
				
			}
		}
		
	}
	
	/**
	 * 层次遍历
	 * 跟先入队，
	 * 循环，节点出队，显示该节点，它的左右儿子入队
	 *  
	 */
    public void levelOrder(TreeNode root){
    	Queue<TreeNode> queue= new LinkedList<TreeNode>();
    	TreeNode temp ;
    	queue.add(root);  //根入队
    	while (!queue.isEmpty()) {
    		temp = queue.poll();     //队头元素出队
    		System.out.print(temp.getData() +" ");
    		if(temp.getLchild() != null){     //左子树不空，则左子树入队列
    			queue.add(temp.getLchild());
            }
            if(temp.getRchild() != null){     //右子树不空，则右子树入队列
            	queue.add(temp.getRchild());
            }
		}
    	
    }

	public static void main(String[] args) {
		// 将一个数组转化为一颗完全二叉树
		Object[] array = { 1, 2, 3, 4, 5, 6, 7, 8 };
		// Object[] array = {'A','B','O','C','S','M','Q','W','K'};

		BinaryTree tree = new BinaryTree();

		TreeNode root = tree.buildTree(array); // 建立二叉树 ，返回根
		System.out.println(tree.tree);
		tree.levelOrder(root);

	}

}
